`
https://leetcode.cn/problems/partition-equal-subset-sum/
`

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function (nums) {
  // 复用 0-1 背包问题的思想
  // 先求出 sum ，把 nums 的每个值看成重量，判断能否刚好装满 num / 2

  const sum = nums.reduce((acc, cur) => acc + cur, 0)
  // 和为奇数时，不可能划分成两个和相等的集合
  if (sum % 2 !== 0) return false

  const n = nums.length
  const bagWeight = Math.floor(sum / 2)

  // dp[i][j] 表示前 i 个物品能否刚好装满 j 个重量
  const dp = new Array(n + 1).fill().map(() => new Array(bagWeight + 1).fill(false))

  // 背包没有空间的时候，就相当于装满了
  for (let i = 0; i <= n; i++)
    dp[i][0] = true

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= bagWeight; j++) {
      // 背包容量不足，不能装入第 i 个物品
      if (j - nums[i - 1] < 0) {
        dp[i][j] = dp[i - 1][j]
      } else {
        // 能装入第 i 个物品，判断是否刚好装满
        dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]]
      }
    }
  }

  return dp[n][bagWeight]
};